class solution2
{
public:
    vector<vector<int>> dirs = {{0,-1},{0,1},{-1,0},{1,0}};
    vector<vector<bool>> visited;
    int m = 0,n = 0;
    int dfs(const vector<vector<char>>& vv,int x,int y,int x2, int y2) 
    {
    	visited[x][y] = true;
        int tmp_length = INT_MAX;
        if(x == x2 && y == y2){
        	return 1;
		}
        for(const auto& e : dirs)
        {
        	int nx = x + e[0];
			int ny = y + e[1];
        	if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && vv[nx][ny] == '.')
        	{
        		tmp_length = std::min(tmp_length,dfs(vv,nx,ny,x2,y2));
			}
		}
		visited[x][y] = false;
		 return tmp_length == INT_MAX ? tmp_length : tmp_length + 1; 
    }
    
    int shortestLengthDFS(vector<vector<char>>& vv,int x1,int y1,int x2,int y2)
    {
        m = vv.size();
        n = vv[0].size();
        visited.resize(m, vector<bool>(n, false));
        visited[x1][y1] = true;
        int length = dfs(vv, x1, y1, x2, y2);
        if (vv[x2][y2] == '#' || length == INT_MAX) {
            return -1;
        }
        return length - 1;
    }
 
};
 
int main() 
{
	vector<vector<char>> vv = 
	{{'.','.','#'},
	 {'.','#','.'},
	 {'#','.','.'}
	};
	cout << solution2().shortestLengthDFS(vv,1,0,2,2) << endl;
	return 0;
}